Tight Hamilton cycles in random uniform hypergraphs

In this paper we show that e/n is the sharp threshold for the existence of tight Hamilton cycles in random k ‐uniform hypergraphs, for all k ≥ 4. When k = 3 we show that 1/n is an asymptotic threshold. We also determine thresholds for the existence of other types of Hamilton cycles. © 2012 Wiley Periodicals, Inc. Random Struct. Alg., 2013     

The size of the giant high‐order component in random hypergraphs

The phase transition in the size of the giant component in random graphs is one of the most well‐studied phenomena in random graph theory. For hypergraphs, there are many possible generalizations of the notion of a connected component. We consider the following: two j‐sets (sets of j vertices) are j‐connected if there is a walk of edges between them such that two consecutive edges intersect in at least j vertices. A hypergraph is j‐connected if all j‐sets are pairwise j‐connected. In this paper, we determine the asymptotic size of the unique giant j‐connected component in random k‐uniform hypergraphs for any and .     

Regularity and projective dimension of edge ideals

In this paper, we study the regularity and projective dimension of edge ideals. We provide two upper bounds for the regularity of edge ideals of vertex decomposable graphs in terms of the induced matching number and the number of cycles. Also, we generalize one of the upper bounds given by Dao and Schweig for the projective dimension of hypergraphs.     

Identifying defective sets using queries of small size

We examine the following version of a classic combinatorial search problem introduced by Rényi: Given a finite set $X$ of $n$ elements we want to identify an unknown subset $Y$ of $X$, which is known to have exactly $d$ elements, by means of testing, for as few as possible subsets $A$ of $X$, whether $A$ intersects $Y$ or not. We are primarily concerned with the non-adaptive model, where the family of test sets is specified in advance, in the case where each test set is of size at most some given natural number $k$. Our main results are nearly tight bounds on the minimum number of tests necessary when $d$ and $k$ are fixed and $n$ is large enough.     

A Solution to a Problem of Jacobson,Kézdy and Lehel

We solve a problem proposed by Jacobson, Kézdy, and Lehel [4] concerning the existence of forbidden induced subgraph characterizations of line graphs of linear k-uniform hypergraphs with sufficiently large minimal edge-degree. Actually, we prove that for each k3 there is a finite set Z(k) of graphs such that each graph G with minimum edge-degree at least 2k²–3k+1 is the line graph of a linear k-uniform hypergraph if and only if G is a Z(k)-free graph.Acknowledgments. We thank the anonymous referees, whose suggestions helped to improve the presentation of the paper.Winter 2002/2003 DIMACS Award is gratefully acknowledged2000 Mathematics Subject Classification: 05C65 (05C75, 05C85)     

Hypergraph list coloring and Euclidean Ramsey theory

A hypergraph is simple if it has no two edges sharing more than a single vertex. It is s‐list colorable (or s‐choosable) if for any assignment of a list of s colors to each of its vertices, there is a vertex coloring assigning to each vertex a color from its list, so that no edge is monochromatic. We prove that for every positive integer r, there is a function d_r(s) such that no r‐uniform simple hypergraph with average degree at least d_r(s) is s‐list‐colorable. This extends a similar result for graphs, due to the first author, but does not give as good estimates of d_r(s) as are known for d₂(s), since our proof only shows that for each fixed r ≥ 2, d_r(s) ≤ 2 We use the result to prove that for any finite set of points X in the plane, and for any finite integer s, one can assign a list of s distinct colors to each point of the plane so that any coloring of the plane that colors each point by a color from its list contains a monochromatic isometric copy of X. © 2011 Wiley Periodicals, Inc. Random Struct. Alg., 2011     

On Graph-Lagrangians and clique numbers of 3-uniform hypergraphs

The paper explores the connection of Graph-Lagrangians and its maximum cliques for 3-uniform hypergraphs.Motzkin and Straus showed that the Graph-Lagrangian of a graph is the Graph-Lagrangian of its maximum cliques.This connection provided a new proof of Turán classical result on the Turán density of complete graphs.Since then,Graph-Lagrangian has become a useful tool in extremal problems for hypergraphs.Peng and Zhao attempted to explore the relationship between the Graph-Lagrangian of a hypergraph and the order of its maximum cliques for hypergraphs when the number of edges is in certain range.They showed that if G is a 3-uniform graph with m edges containing a clique of order t-1,then λ(G)=λ([t-1]~((3))) provided (t-13)≤m≤(t-13)+_(t-22).They also conjectured:If G is an r-uniform graph with m edges not containing a clique of order t-1,then λ(G)λ([t-1]~((r))) provided (t-1r)≤ m ≤(t-1r)+(t-2r-1).It has been shown that to verify this conjecture for 3-uniform graphs,it is sufficient to verify the conjecture for left-compressed 3-uniform graphs with m=t-13+t-22.Regarding this conjecture,we show: If G is a left-compressed 3-uniform graph on the vertex set [t] with m edges and |[t-1]~((3))\E(G)|=p,then λ(G)λ([t-1]~((3))) provided m=(t-13)+(t-22) and t≥17p/2+11.     

Isomorphic edge disjoint subgraphs of hypergraphs

We show that any k‐uniform hypergraph with n edges contains two isomorphic edge disjoint subgraphs of size for k = 4, 5 and 6. This is best possible up to a logarithmic factor due to an upper bound construction of Erd?s, Pach, and Pyber who show there exist k‐uniform hypergraphs with n edges and with no two edge disjoint isomorphic subgraphs with size larger than . Furthermore, our result extends results Erd?s, Pach and Pyber who also established the lower bound for k = 2 (eg. for graphs), and of Gould and Rödl who established the result for k = 3. © 2016 Wiley Periodicals, Inc. Random Struct. Alg., 48, 767–793, 2016     

Two Questions of Erdős on Hypergraphs above the Turán Threshold

For ordinary graphs it is known that any graph G with more edges than the Turán number of must contain several copies of , and a copy of , the complete graph on vertices with one missing edge. Erd?s asked if the same result is true for , the complete 3‐uniform hypergraph on s vertices. In this note, we show that for small values of n, the number of vertices in G, the answer is negative for . For the second property, that of containing a , we show that for the answer is negative for all large n as well, by proving that the Turán density of is greater than that of .